From 33c5872a65e0e063bd07e82ffd1006e30e2384d1 Mon Sep 17 00:00:00 2001 From: tsteven4 <13596209+tsteven4@users.noreply.github.com> Date: Tue, 25 Feb 2020 18:53:32 -0700 Subject: [PATCH] optimize simplify filter. drop unused member ordinal from xte struct. This, and changes in the implementation of shuffle_xte, result in a ~13% speed improvement for long routes. use new/delete instead of *alloc/free. provide initializers for all data members. use strtol instead of atol. update casting to c++. --- smplrout.cc | 70 +++++++++++++++++++++++------------------------------ smplrout.h | 23 +++++++++--------- 2 files changed, 41 insertions(+), 52 deletions(-) diff --git a/smplrout.cc b/smplrout.cc index 9ad6c2b86..172033483 100644 --- a/smplrout.cc +++ b/smplrout.cc @@ -56,10 +56,16 @@ 2008/08/20: added "relative" option, (Carsten Allefeld, carsten.allefeld@googlemail.com) */ +#include // for qsort, strtol +#include // for swap + +#include // for QDateTime + #include "defs.h" -#include "grtcirc.h" #include "smplrout.h" -#include +#include "grtcirc.h" // for gcdist, linedist, radtometers, radtomiles, linepart +#include "src/core/datetime.h" // for DateTime + #if FILTERS_ENABLED #define MYNAME "simplify" @@ -68,7 +74,7 @@ void SimplifyRouteFilter::free_xte(struct xte* xte_rec) { - xfree(xte_rec->intermed); + delete xte_rec->intermed; } #define HUGEVAL 2000000000 @@ -78,8 +84,7 @@ void SimplifyRouteFilter::routesimple_waypt_pr(const Waypoint* wpt) if (!cur_rte) { return; } - xte_recs[xte_count].ordinal=xte_count; - xte_recs[xte_count].intermed = (struct xte_intermed*) xmalloc(sizeof(struct xte_intermed)); + xte_recs[xte_count].intermed = new struct xte_intermed; xte_recs[xte_count].intermed->wpt = wpt; xte_recs[xte_count].intermed->xte_rec = xte_recs+xte_count; xte_recs[xte_count].intermed->next = nullptr; @@ -151,25 +156,27 @@ void SimplifyRouteFilter::compute_xte(struct xte* xte_rec) int SimplifyRouteFilter::compare_xte(const void* a, const void* b) { - double distdiff = ((struct xte*)a)->distance - - ((struct xte*)b)->distance; - int priodiff = ((struct xte*)a)->intermed->wpt->route_priority - - ((struct xte*)b)->intermed->wpt->route_priority; + const auto* xte_a = static_cast(a); + const auto* xte_b = static_cast(b); - if (HUGEVAL == ((struct xte*)a)->distance) { + if (HUGEVAL == xte_a->distance) { return -1; } - if (HUGEVAL == ((struct xte*)b)->distance) { + if (HUGEVAL == xte_b->distance) { return 1; } + int priodiff = xte_a->intermed->wpt->route_priority - + xte_b->intermed->wpt->route_priority; if (priodiff < 0) { return 1; } if (priodiff > 0) { return -1; } + + double distdiff = xte_a->distance - xte_b->distance; if (distdiff < 0) { return 1; } @@ -197,42 +204,25 @@ void SimplifyRouteFilter::routesimple_head(const route_head* rte) return; } - xte_recs = (struct xte*) xcalloc(rte->rte_waypt_ct, sizeof(struct xte)); + xte_recs = new struct xte[rte->rte_waypt_ct]; cur_rte = rte; } void SimplifyRouteFilter::shuffle_xte(struct xte* xte_rec) { - struct xte tmp_xte; while (xte_rec > xte_recs && compare_xte(xte_rec, xte_rec-1) < 0) { - tmp_xte.distance = xte_rec->distance; - tmp_xte.ordinal = xte_rec->ordinal; - tmp_xte.intermed = xte_rec->intermed; - xte_rec->distance = xte_rec[-1].distance; - xte_rec->ordinal = xte_rec[-1].ordinal; - xte_rec->intermed = xte_rec[-1].intermed; - xte_rec->intermed->xte_rec = xte_rec; + std::swap(xte_rec[0], xte_rec[-1]); + xte_rec[0].intermed->xte_rec = &xte_rec[0]; + xte_rec[-1].intermed->xte_rec = &xte_rec[-1]; xte_rec--; - xte_rec->distance = tmp_xte.distance; - xte_rec->ordinal = tmp_xte.ordinal; - xte_rec->intermed = tmp_xte.intermed; - xte_rec->intermed->xte_rec = xte_rec; } while (xte_rec - xte_recs < xte_count-2 && compare_xte(xte_rec, xte_rec+1) > 0) { - tmp_xte.distance = xte_rec->distance; - tmp_xte.ordinal = xte_rec->ordinal; - tmp_xte.intermed = xte_rec->intermed; - xte_rec->distance = xte_rec[1].distance; - xte_rec->ordinal = xte_rec[1].ordinal; - xte_rec->intermed = xte_rec[1].intermed; - xte_rec->intermed->xte_rec = xte_rec; + std::swap(xte_rec[0], xte_rec[1]); + xte_rec[0].intermed->xte_rec = &xte_rec[0]; + xte_rec[1].intermed->xte_rec = &xte_rec[1]; xte_rec++; - xte_rec->distance = tmp_xte.distance; - xte_rec->ordinal = tmp_xte.ordinal; - xte_rec->intermed = tmp_xte.intermed; - xte_rec->intermed->xte_rec = xte_rec; } } @@ -280,9 +270,9 @@ void SimplifyRouteFilter::routesimple_tail(const route_head* rte) totalerror += xte_recs[i].distance; } } - (*waypt_del_fnp)((route_head*)(void*)rte, - (Waypoint*)(void*)(xte_recs[i].intermed->wpt)); - delete (Waypoint*)(void*)(xte_recs[i].intermed->wpt); + (*waypt_del_fnp)(const_cast(rte), + const_cast(xte_recs[i].intermed->wpt)); + delete xte_recs[i].intermed->wpt; if (xte_recs[i].intermed->prev) { xte_recs[i].intermed->prev->next = xte_recs[i].intermed->next; @@ -304,7 +294,7 @@ void SimplifyRouteFilter::routesimple_tail(const route_head* rte) free_xte(xte_recs+xte_count); } while (xte_count); } - xfree(xte_recs); + delete[] xte_recs; } void SimplifyRouteFilter::process() @@ -335,7 +325,7 @@ void SimplifyRouteFilter::init() } if (countopt) { - count = atol(countopt); + count = strtol(countopt, nullptr, 10); } if (erroropt) { int res = parse_distance(erroropt, &error, 1.0, MYNAME); diff --git a/smplrout.h b/smplrout.h index 1acd675f0..928646ec8 100644 --- a/smplrout.h +++ b/smplrout.h @@ -82,11 +82,11 @@ private: double totalerror = 0; double error = 0; - char* countopt; - char* erroropt; - char* xteopt; - char* lenopt; - char* relopt; + char* countopt = nullptr; + char* erroropt = nullptr; + char* xteopt = nullptr; + char* lenopt = nullptr; + char* relopt = nullptr; void (*waypt_del_fnp)(route_head* rte, Waypoint* wpt); QVector args = { @@ -115,16 +115,15 @@ private: struct xte_intermed; struct xte { - double distance; - int ordinal; - struct xte_intermed* intermed; + double distance{0.0}; + struct xte_intermed* intermed{nullptr}; }; struct xte_intermed { - struct xte* xte_rec; - struct xte_intermed* next; - struct xte_intermed* prev; - const Waypoint* wpt; + struct xte* xte_rec{nullptr}; + struct xte_intermed* next{nullptr}; + struct xte_intermed* prev{nullptr}; + const Waypoint* wpt{nullptr}; }; void free_xte(struct xte* xte_rec); -- 2.30.2